#include <iostream>

using ll = long long;

auto &is = std::cin;
auto &os = std::cout;

template<class T,size_t size>
struct greater_array{
    T arr[size*2];
    T&operator[](ll n)noexcept{
        return arr[n+size];
    }
};

const ll max_n {13+5};
ll n;
greater_array<bool, max_n*3> l,zx,yx;
ll ans[max_n], sum;


void dfs(const ll x)noexcept{
    if(x>n){
        sum++;
        if(sum<=3){
            for(ll i{1};i<=n;i++){
                os<<ans[i]<<' ';
            }
            os<<'\n';
        }
        return;
    }
    for(ll j{1};j<=n;j++){
        if(l[j]||zx[x+j]||yx[x-j])continue;
        ans[x] = j;
        l[j]=zx[x+j]=yx[x-j]=true;
        dfs(x+1);
        l[j]=zx[x+j]=yx[x-j]=false;
    }
    return;
}

int main(){
    is>>n;
    dfs(1);
    os<<sum<<'\n';
}